import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * 电话号码的字母组合
 * 给定一个仅包含数字2-9的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
 *
 * 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母
 *
 */
public class LetterCombinations {
    ArrayList<String> res = new ArrayList<>();
    StringBuilder temp = new StringBuilder();
    public List<String> letterCombinations(String digits) {
        String[] numString = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        if(digits.equals("")) return new ArrayList<>();
        backTracking(numString,digits,0);

        return res;
    }

    public void backTracking(String[] numString,String digits,int index){
        if(temp.length()==digits.length()){
            res.add(new String(temp));
            return ;
        }

        char c = digits.charAt(index);
        String s = numString[c - '0'];

        for (int i = 0; i < s.length(); i++) {
            temp.append(s.charAt(i));
            backTracking(numString,digits,index+1);
            temp.deleteCharAt(temp.length()-1);
        }
    }
}
